---
title: "7、爬山"
created: 2025-11-28
tags:
  - 算法
---

# 7、爬山

## 题目 爬山

![[image-4f162199.png]]

## 思路分析

模拟 贪心 堆

hack题 被选手发现有个数据能卡正解 笑了

## 代码实现

```cpp
 /*

有点像砍竹子

x轴上 n座山 每座山高为hi 从左到右花费的体力 前缀和

可以降低某座山的高度为

 (1) 下取整floor 的根号h floor(sqrt(hi))   有P次

 (2) 下取整的 二分之h    floor(hi/2)       有Q次

每座山都可以无限次做 但限制在于魔法的可用次数

如果两种次数是一起算的 就直接贪心 每次对最高的做 并且做  max( floor(sqrt(hi)) ,  floor(hi/2) )

但两种次数分开算 就需要抉择 可能是dp

但这个数据范围也不像是能dp

直接贪心做了 每次对最高的做 选两个方案里最优的做（有的话就做最优的 没有的话 另一种也是当前最优了）

前缀和跟差分能用吗

用：

前缀和预处理在读入的时候做

砍去山等于 做一个差分 可是差分数组要从前缀和数组里构造出来 一层for

差分完后得到原答案 又得做一遍前缀和 二层for

不用：

直接读入山

砍去山

累加 一层for

没必要用前缀和 负优化

每次找最大的山

在h[]数组保序的基础上(好像不需要存 答案是累计 顺序无关紧要） 用优先队列维护

直接用优先队列存所有的山的高度 每次取出最高的山 选择做法 再把做完的放回优先队列

*/

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

int n,P,Q;

priority_queue<int> h;

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>P>>Q;

	while(n--){

		int x;cin>>x;

		h.push(x);

	}

	while(Q || P){

//		cout<<h.top()<<endl;  h.pop();

		int curh=h.top();h.pop();

//		cout<<"当前最高: "<<curh<<endl;

		int choice1=floor(sqrt(curh));

		int choice2=floor(curh/2);

		int well=min(choice1,choice2);

		if(well==choice1){//如果更大的是第一种操作

			if(P){//且P存在

				h.push(choice1);

				P--;

			}

			else if(Q){//P操作次数没了 退而求其次 若Q存在 做Q

				h.push(choice2);

				Q--;

			}

			else{//全操作完了 break;

				break;

			}

		}

		else if(well==choice2){

			if(Q){

				h.push(choice2);

				Q--;

			}

			else if(P){

				h.push(choice1);

				P--;

			}

			else{//全操作完了 break;

				break;

			}

		}

	}

	long long res=0;

	while(!h.empty()){

//		cout<<h.top()<<" ";

		res+=h.top();

		h.pop();

	}

	cout<<res;

	return 0;

 }
```

## 同类题型

## 视频讲解

---
⬅️ [[6、数字接龙|6、数字接龙]] 🏠 [[00-刷题理模型]] ➡️ [[8、拔河|8、拔河]]